Міністерство Освіти України Національний університет «Львівська політехніка» Методичні вказівки До лабораторної роботи № 7 На тему: «Методи сортуваня. Сортування підрахунком» з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» ЗАТВЕРДЖЕНО на засіданні кафедри програмного забезпечення протокол № від 2008 року місто Львів 2008 рік Методичні вказівки до лабораторної роботи з дисципліни «Алгоритми і структури даних» Для базового напрямку 6.0804 «Комп’ютерні науки» Укладачі: Семчишин Ю. Б. Коротєєва Т. О. Вовчак І. Г. Відповідальний за випуск: Рецензенти: Тема роботи: Ознайомлення із методами сортування. Алгоритм сортування пірахунком Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування підрахунком. Виконати лабораторну роботу використавши здобуті знання з методів сортування, зокрема методу сортування підрахунком. ТЕОРЕТИЧНІ ВІДОМОСТІ Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів. Ідея алгоритму полягає в наступному: спочатку підрахувати скільки разів кожен елемент (ключ) зуcтрічається в вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця. Обчислювальна складність роботи алгоритму становить O(N + K), де N — довжина масиву, та K — величина діапазону. В алгоритмі використовуються додатковий масив, тому ємнісна складність становить E(N + K). В такій реалізації алгоритм є стабільним (не змінює порядок елементів з однаковим ключем). Використання даного алгоритму є доцільним тільки у випадку малих K. РЕКОМЕНДОВАНІ ДЖЕРЕЛА http://www.wikipedia.org/. Donald Ervin Knuth «The Art of Computer Programming». 2. ВКАЗІВКИ ДО ВИКОНАННЯ РОБОТИ При реалізації алгоритму застосувати здобуті знання на лабораторній роботі. Тобто у всіх завданнях необхідно реалізувати алгоритм сортування підрахунком. Використовувати мову програмування C/C++. Лабораторна робота вважається зданою при наявності програмного продукту звіту і проведеного відповідного захисту виконаної роботи. 3. ПОСЛІДОВНІСТЬ ВИКОНАННЯ РОБОТИ Отримати індивідуальне завдання у викладача; Уточнити завдання (можливі різні трактування завдання); Написати програмну реалізацію виконання індивідуального завдання із використанням вивченого методу (алгоритму) на даній лабораторній роботі; Протестувати на наявність логічних помилок програми; Оформити звіт відповідно до стандарту; Захистити виконану роботу. 4. КОНТРОЛЬНІ ПИТАННЯ Які ви знаєте методи сортування? Який метод сортування був розглянений на даній лабораторній роботі? Від чого прямо – залежним являється швидкість сортування? Опишіть характеристики даного методу. Порівняєте даний метод із іншими методами сортування вам відомими. Наскільки являється ефективним даний метод сортування? Чи використовують даний метод на практиці, і наскільки часто? Чи можлива оптимізації даного методу? Якщо так, то яка? Якщо ні, то по яких причинах? Чим оригінальним виділяється даний метод від інших?